package year2023.recursion;


/*
9.8硬币表示 #
假设我们有8种不同面值的硬币｛1，2，5，10，20，50，100，200｝，
用这些硬币组合构成一个给定的数值n。
例如n=200，那么一种可能的组合方式为 200 = 3 1 + 1＊2 + 1＊5 + 2＊20 + 1 50 + 1 * 100.
问总共有多少种可能的组合方式？

[华为面试] 1分2分5分硬币三种组合成1角，共有多少种组合

[创新工厂笔试] 1分，2分，5分，10分，四种硬币，给定n分钱，有多少种组合

 */

public class Code03_CoinDeliver {

    public static void main(String[] args) {
        Code03_CoinDeliver obj = new Code03_CoinDeliver();
        for (int i = 0; i < 25; i++) {
            int ways = obj.countWays(i);
            System.out.println(i + "---" + ways);
        }
    }

    //recursion
    public int countWays(int n){
        if (n <= 0) return 0;
        return countWaysCore(n, new int[]{1,5,10,25},3);
    }

    private int countWaysCore(int n, int[] coins, int cur){
        if (cur == 0) return 1;
        int res = 0;
        //不选coins[cur]
        //要一个
        //要两个  ...
        for (int i = 0; i*coins[cur] <= n; i++) {
            //剩余数
            int surplus = n - i * coins[cur];
            res += countWaysCore(surplus, coins, cur - 1);
        }
        return res;
    }

    //iteration


}
